package leetcode.jianzhioffer;

import javax.management.modelmbean.ModelMBean;

/**
 * @program: datastructureandalogorithm
 * @description:
 * @author: hmx
 * @create: 2021-10-29 10:00
 **/
public class JianZhiOffer10I {

    int mod = 1000000007;
    /*
    int[] nums = null;
    public int fib(int n) {
        initNums(n);
        if (n < 2) {
            nums[n] = n;
            return n;
        }
        if (nums[n - 1] == 0) {
            nums[n - 1] = fib(n - 1);
        }
        if (nums[n - 2] == 0) {
            nums[n - 2] = fib(n - 2);
        }
        return (nums[n - 1] + nums[n - 2])  % mod;
    }

    private void initNums(int n) {
        if (nums == null) {
            nums = new int[n + 1];
        }
    }*/

    /*public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0;
        int q = 0;
        int r = 1;
        for (int i = 1; i < n; i++) {
            p = q;
            q = r;
            r = (q + p) % mod;
        }
        return r;
    }*/

    /*public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int p = 0;
        int q = 0;
        int r = 1;
        for (int i = 1; i < n; i++) {
            p = q;
            q = r;
            r = (q + p) % mod;
        }
        return r;
    }*/

    public int fib(int n) {
        if (n < 2) {
            return n;
        }
        int[][] a = {{1,1},{1,0}};
        int[][] res = pow(a, n - 1);
        //res[0][0]即为fib(n)的值
        return res[0][0];
    }

    //矩阵的幂次方
    private int[][] pow(int[][] a, int n) {
        //任何二维矩阵乘以当前矩阵都是其本身
        int[][] res = {{1, 0}, {0, 1}};
        while (n > 0) {
            //当为奇数的时候,将当前a矩阵赋给res矩阵
            if ((n & 1) == 1) {
                res = multiply(res, a);
            }
            n >>= 1;
            a = multiply(a, a);
        }
        return res;
    }

    //矩阵相乘
    private int[][] multiply(int[][] a, int[][] b) {
        int[][] c = new int[2][2];
        for (int i = 0; i < 2; i++) {
            for (int i1 = 0; i1 < 2; i1++) {
                c[i][i1] = (int) (((long) a[i][0] * b[0][i1] + (long) a[i][1] * b[1][i1]) % mod);
            }
        }
        return c;
    }

    public static void main(String[] args) {
        long begin = System.currentTimeMillis();
        JianZhiOffer10I offer = new JianZhiOffer10I();
        System.out.println("offer.fib(5) = " + offer.fib(45));
        long cost = System.currentTimeMillis() - begin;
        System.out.println("cost = " + cost);
    }
}
